package com.zrkizzy.linkedlist;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;



/**
 * 剑指 Offer 06. 从尾到头打印链表
 *
 * @author zhangrongkang
 * @date 2022/11/14
 */
public class 剑指Offer06从尾到头打印链表 {
    class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
        }
    }

    /**
     * 递归
     */
    class Solution01 {
        /**
         * 定义用于存储返回结果的集合
         */
        private List<Integer> list = new ArrayList<>();

        public int[] reversePrint(ListNode head) {
            recursion(head);
            int[] result = new int[list.size()];
            for (int i = 0; i < result.length; i++) {
                result[i] = list.get(i);
            }
            return result;
            // stream返回方式
            // return list.stream().mapToInt(Integer::intValue).toArray();
        }

        // 递归获取
        private void recursion(ListNode node) {
            // 递归到底的情况
            if (node == null) {
                return;
            }
            // 递归链表下一个节点
            recursion(node.next);
            // 存储当前节点的值
            list.add(node.val);
        }
    }

    /**
     * 辅助栈
     */
    class Solution02 {
        /**
         * 定义用于存储返回结果的集合
         */
        private Stack<Integer> stack = new Stack<>();

        public int[] reversePrint(ListNode head) {
            // 遍历整个链表并将链表添加到辅助栈中
            while (head != null) {
                stack.push(head.val);
                head = head.next;
            }
            int i = 0;
            int[] result = new int[stack.size()];
            // 遍历辅助栈
            while (!stack.isEmpty()) {
                result[i++] = stack.pop();
            }
            return result;
        }
    }

}

